COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\|\\@macros.pox[1,rwg]\⊂'10545\←=-5\λ\F1\←H\→a\F3\←H\/=3\+a\ε\F1\
C00020 ENDMK
C⊗;
\|\\@macros.pox[1,rwg];\⊂'10545;\←=-5;\λ\F1\←H\→a\F3\←H\/=3;\+a\ε\F1\;
\|\\M0BDR40;\M1basl30;\M3BASI30;\M2basb30;\M4SUP;\M5SUB;\M6misc25;\M7grk30;\M8fix20;\.
\←=1;\→P\∞EVERYPAGE[\P\←=1;\+P\→P\oEP<1\DP>\WEP,R=125;\p]\;
\C\F0Relativistic Systems of Automata\F1

\J	We are taking an idea from the theory of relativity and applying it to systems of
interacting automata.  The idea is that instead of having a single time variable
of which the state at every position in space is a function, each body
has its own \F3local time\F1 and there is no notion of simultaneity for events
separated in space.  The following notion does not depend on understanding
anything about relativity theory, and after we have explained it we will say what
it might be good for.

	We start with a collection of entities \f2A\f5i which are the automata of the
system.  Each \f2A\f5i has a set \F2states (A\F5i\F2)\F1 which is the set of its
possible states.  Another set associated with \f2A\f5i is \F2times (A\F5i\F2)\F1
which has a partial ordering for which < is used.  A state history of an
automaton A\f5i is a map.  \F2Statehis: times(A\f5i)\f1→states(A\f5i)\F1.  (In the
usual \F3non-relativistic\F1 automata theory, each \F2times (A\F5i\F2)\F1
is the set of integers and there is a distinguished isomorphism between \F2times
(A\F5i\F2)\F1 and a universal set \F2times\F1 isomorphic to the integers.)
There are two main cases of interest for \F2times (A\F5i\F2)\F1, namely the
integers and the real numbers.  Some subautomata of a system may have integer
times while others may have real times.  Even if both have integer times they may
not correspond in a simple way - one clock may tick every second at WWV in
Boulder Colorado and the other may tick once a school day in Rio de Janeiro.

	In the examples we have given, the ordering is total, but you will see
that a system of automata can best be regarded as having partial ordered time
even though its subautomata have total ordered times.  Therefore, if we want
to take systems of automata as the constituent subautomata of yet bigger 
systems, the basic construction should use partial ordering.

	Besides the sets \F2states(A\F5i\F2)\F1 and \F2times(A\F5i\F2)\F1, we also
have the sets \F2inputs(A\F5i\F2) and \F2outputs(A\F5i\F2)\F1 which give the possible
values of inputs and outputs.  An input history of A\f5i is a map
\F2inhis: times(A\f5i)\f1→inputs(A\f5i)\F1 and an output history is a map
\F2outhis: times(A\f5i)\f1→outputs(A\f5i)\F1.
If we need it, we can use the concept of a \F2history\F1 of
\f2A\f5i which is a map\.

\C\F2hist: times(A\f5i)→inputs(A\f5i)⊗states(A\f5i)⊗outputs(A\f5i)\F1

\JLet \F2Inhis(A\f5i), Statehis(A\f5i), Outhis(A\f5i)\F1 and \F2His(A\f5i)\F1 (written
with initial caps) be the sets of all possible input histories, state histories,
output histories, and histories.

	The law of motion of an automaton gives the state at any local time as a 
function of the input history and the state history.  We impose the further
condition that the state at a given time depend only on the past of the state and
the input.  If the local time is taken as an integer, then the most important case
is when the state depends only on the immediately preceding state and input.
Moreover, the general case of integer time can be reduced to the case of 
depending only on the immediately preceding time by replacing the automaton A\f5i
by an automaton A\Q.'\q.\f5i\F1 whose states are complete pasts of the states
of A\f5i.  While this reduction is conceptually always possible, it may be
computationally simpler not to do it in a particular case (if we ever get to a
particular case).

	When we have a continuous time and the state is given by a real variable
or vector of real variables, then a main case of interest is when we have 
a differential equation\.

\C\!jdiv((\F1d state),(\F1dt));  =  F(state, input, t)

\J(In order to be sure only the past is involved you could specify a left hand
derivative, but it won't matter if all the functions are smooth enough.)

	The output law of an automaton gives the output as a function of the
state.  (Something might be gained by letting the output depend on the pasts of
the state and input if it is computationally or mathematically convenient in
a particular case.)

	The interaction between automata is specified by a law which gives the
input of A\f5i as a function of the output histories of all the automata subject
to a causality condition.  The idea of the causality condition is again to allow 
the state to depend only on the past, but since we do not have a correspondence
between the times of the different automata, we proceed as follows:

	Form the disjoint union of all the local time spaces and take a partial ordering
\f6< on that space consistent with the local orderings of local timer, i.e. 
if \F2t\f5i ε times (A\f5i)\F1 and \F2t\Q.'\q.\F2\f5i ε times (A\f5i)\F1, then
\F2t\f5i \f6< t\Q.'\q.\f5i \F8\↑=5;≡\⊗ \F2t\f5i < t\Q.'\q.\f5i\F1.  
This can be done trivially
by taking t \f6< t\Q.'\q.\F1 if and only if t and t\Q.'\q.\F1 are in the same
\F2times (A\f5i)\F1 and t < t', but in the trivial case the automata won't
interact.

	We now require that for any t \f3ε \F2times (A\f5i)\f1, input\f5i(t)\F1
depend only on \F2output\f5j(T)\F1 for values T satisfying T\f6<t.

	In the integer time non-relativistic case, the correspondence between
the local times reduces the ordering \f6< to the ordering <, and instead of
letting input\f5i(t\f5i) depend on the entire pasts of the outputs of the
automata, it depends only on the outputs at the immediately preceding time.

	We can express this \F3immediacy\F1 condition in the relativistic case
by introducing a function \f7J\f5i\f5j(t\f5i) and requiring that input\f5i(t\f5i)
depend precisely on the output\f5j(\f7J\f5i\f5j(t\f5i)) for all j's.  The
function \f7J\f5i\f5j(t\f5i) can be used to determine the partial ordering \f6<,
and any \f7J\f5i\f5j will do provided it allows no cycles whereby the future or
the present of an automaton can affect its present.

	The formalism includes partial differential equations of the sort where\.

\C\!jdiv((\F1∂u),(\F1∂t));  =  F(x, y, \!jdiv((\F1∂f),(\F1∂x));,\N
 \!jdiv((\F1∂f),(\F1∂y));, \!jdiv((\F1∂\F42\F1f),(\F1∂x\F42\F1));, etc).

\JWe then have to attach an automaton to each point of space.  (The physics minded
reader should imagine Maxwell's equations considered this way, but 
may find himself discouraged by the fact
that the automata don't retain their identity under Lorentz transformations.  Clearly,
this is something to worry about in the general relativistic theory of automata).

Equivalence of automaton systems

	Let A and B be automaton systems.  Suppose there is a 1-1 map \f7J of
the set H(A) of histories of A onto H(B) satisfying the following causality
condition:  there are functions \f7J\f5i\f5j(t\f5i) and \f7Y\f5j\f5i(t\f5i)
such that the state of A\f5i at local time t\f5i depends only on the states of B\f5j's
at times preceding \f7J\f5i\f5j(t\f5i) and the state of B\f5j at local time t\f5j 
depends only on the states of the A\f5j's at times preceding \f7Y\f5j\f5i(t\f5i).
The case in which the state of A\f5i at time t\f5i depends on the states of the
B\f5j's at the times \f7J\Q.'\q.\f52\F1\f5j(t\f5i) only and the state B\f5j at time
t\f5j depends on the states of the A\f5i's at the times \f7Y\Q.'\q.\f5j\f5i\F1(t\f5j)
only will be called the immediate case.

	When two automaton systems correspond in this way we shall call them
equivalent.  Note that there need be no correspondence between the subautomata
of one system and those of the other.  (If we regard Maxwell's equations in two
different co-ordinate systems related by a Lorentz transformation defining
automaton systems, the systems will be equivalent.)


Space-like surfaces

	A space-like surface S is an assignment T\f5i of local times to the
automata A\f5i such that the value of state\f5i(T\f5i) depends only on values
of the states of the other automata A\f5j for times prior to T\f5j.  In the
relativity case, an assignment of values of a field on a spacelike surface
allows the field to be determined for future times.  In the automaton
case the situation is more complicated; we must also specify any outputs that may
be required for continuation, and the times for which those outputs are required
may go arbitrarily far back in the local times of the automata.  Obviously some
restrictions on the times for which outputs are required would make computation
simpler.

An example

	She and he are lovers by correspondence.  She writes to him every day, but
he receives the mail and writes a letter only on Saturday.  The letter he writes
on Saturday arrives the following Thursday morning and the letters she writes
by Tuesday arrive Saturday morning but subsequent letters arrive only the following
Saturday.  Her love for him and his love for her are each given by a non-negative
integer.  In each letter he transmits his love for her and she her love for him
except that if his love is greater than 100, he also transmits a proposal of marriage.  If
she receives a proposal she accepts it if her love is greater than 100 and declines
it otherwise.  The game ends with an accepted proposal or if both loves reach 0.
Her love declines by one unit each day she doesn't receive a letter.  When she
receives a letter her love is increased by\.

\C[\!jdiv((\F8m),(\F82));],

\Jwhere m is the amount of love in the letter unless the letter contains a proposal
in which case her love is doubled.  His love is\.\;

\Cmax([\!jdiv((\F81),(\F82));m + \!jbar((\F3l ));- 50r], 0),

\Jwhere m is his love
of the preceding week, \!jbar((\F3l ));is the average love in the letters he
receives and r
is 1 if a letter contains a rejection of a proposal and 0 otherwise.  Initially
she doesn't love him, but he sees her picture which inspires an amount of love m\f5o
and the romance starts.  What values of m\f5o lead to marriage?

	His local time is measured in weeks and hers in days.  If we start her
local time at T=0 on the Thursday she receives his first letter and his at t=0
when he sends his first letter, then the course of the affair is described
by the equations\.

1)	m(t) = \F2if\F1 t=0 \F2 \Q.then \F1m\f5o
\q.\F2else \F1max(0,[\!jdiv((\F81),(\F82));m(t-1) \Q.+ \!jdiv((\F81),(\F87));\N
(\F3l\F1(7t-9) + \F3l\F1(7t-10) + ...\N
 + \F3l\F1(7t-15))
\q.+ (\F2if\F1 r(t7-14)=1 \F2then\F1 -50 \F2else\F1 0)]),

2)	p(t) = \F2if\F1 m(t) > 100 \F2then\F1 1 \F2else\F1 0,

3)	\f3l(T) = \F2if\F1 7|T \Q.\F2then\F1 (\F1if\F1 p(\!jdiv((\F8T),(\F87));)=\N
\F2then\F1 2\F3l\F1(T-1) \F2else\F1 \F3l\F1(T-1) + \N
[\!jdiv((\F81),(\F82));m(\!jdiv((\F8T),(\F87));)])
\q.\F2else\F1 max(0, \F3l\F1(T-1)-1),

and

4)	r(T) = \F2if\F1 7|T ∧ p(\!jdiv((\F8T),(\F87));\N
) ∧ \F3l\F1(T) ≤ 100 \F2then\F1 1 \F2else\F1 0.